package org.example.myleet.rosalind.ctbl;

import org.example.myleet.rosalind.utils.NewickTreeNode;
import org.example.myleet.rosalind.utils.NewickTreeUtil;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String line = br.readLine();
        //解析树
        NewickTreeNode root = NewickTreeUtil.parse(null, line);
        //遍历一次树以得到：n-有值的点的数量，labels、labelMapIndex-值的字典序排序及其对应的下标，trivialNodes-用于分界的点（无值）
        int n = 0;
        List<String> labels = new ArrayList<>();
        List<NewickTreeNode> trivialNodes = new ArrayList<>();
        Queue<NewickTreeNode> queue = new LinkedList<>();
        for (NewickTreeNode child : root.getChildren()) {
            queue.offer(child);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                NewickTreeNode cur = queue.poll();
                if (cur.getValue().length() < 1) {
                    trivialNodes.add(cur);
                } else {
                    labels.add(cur.getValue());
                    ++n;
                }
                if (null != cur.getChildren()) {
                    for (NewickTreeNode child : cur.getChildren()) {
                        queue.offer(child);
                    }
                }
            }
        }
        //字典序排序
        labels.sort(Comparator.naturalOrder());
        //对应的下标
        Map<String, Integer> labelMapIndex = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            labelMapIndex.put(labels.get(i), i);
        }
        for (NewickTreeNode trivialNode : trivialNodes) {
            //逐个进行切分
            trivialSplit(trivialNode, n, labelMapIndex);
        }
        br.close();
    }

    private static void trivialSplit(NewickTreeNode trivialNode, int n, Map<String, Integer> labelMapIndex) {
        int[] res = new int[n];
        Queue<NewickTreeNode> queue = new LinkedList<>();
        queue.offer(trivialNode);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                NewickTreeNode cur = queue.poll();
                if (null != cur.getValue() && cur.getValue().length() > 0) {
                    //属于切分点的子节点且有值，这些值被切分到一起，标记为1
                    int idx = labelMapIndex.get(cur.getValue());
                    res[idx] = 1;
                }
                if (null != cur.getChildren()) {
                    for (NewickTreeNode child : cur.getChildren()) {
                        queue.offer(child);
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            System.out.print(res[i]);
        }
        System.out.println();
    }
}
